package com.example.lib5.search.test.testF;

public class InsertValueSearchF {
    public static void main(String[] args) {
        //创建数组
        int[] arr = new int[8000];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=i;
        }
//        System.out.println(Arrays.toString(arr));
        //执行插值查找算法
        int findIndex = insertValueSearch(arr, 0, arr.length - 1, 100);
        System.out.println(findIndex);
    }

    private static int insertValueSearch(int[] arr, int left, int right, int findValue) {
        //判断是否可以继续找
        if (left>right||findValue<arr[0]||findValue>arr[right]){
            System.out.println("表示找不到");
            return -1;
        }
        //获取中间值，中间index
        //(left+right)/2=
        int mid=left+(left+right)*(findValue-arr[left])/(arr[right]-arr[left]);
        int midValue=arr[mid];
        //递归查找
        if (findValue>midValue){
            return insertValueSearch(arr,mid+1,right,findValue);
        }else if (findValue<midValue){
            return insertValueSearch(arr,left,mid-1,findValue);
        }else {
            return midValue;
        }
    }


}
